package pro.softzhang.algo.lc700;

import pro.softzhang.algo.common.Node;
import pro.softzhang.algo.common.Utils;

/**
 * TODO 加练
 */
public class LC708_InsertIntoASortedCircularLinkedList {
    public static void main(String[] args) {
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        n1.next = n2;
        n2.next = n3;
        n3.next = n1;
        Node head = new Solution().insert(n1, 4);
        Utils.printDoublyLinkedList(head);
    }

    static class Solution {
        public Node insert(Node head, int insertVal) {
            Node node = new Node(insertVal);
            if(head == null) {
                head = node;
                head.next = head;
            } else if(head.next == head) {
                head.next = node;
                node.next = head;
            } else {
                insert0(head, node);
            }
            return head;
        }

        private void insert0(Node head, Node node) {
            Node current = head, next = head.next, biggest = head;
            while (!(current.val <= node.val && next.val >= node.val) && next != head) {
                current = next;
                next = next.next;
                if(current.val >= biggest.val) {
                    biggest = current;
                }
            }
            if(current.val <= node.val && next.val >= node.val) {
                current.next = node;
                node.next = next;
            } else {
                node.next = biggest.next;
                biggest.next = node;
            }
        }
    }
}
